// 给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

// 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

// 示例 1:

// 输入: [3,2,3]
// 输出: [3]
// 示例 2:

// 输入: [1,1,1,3,3,2,2,2]
// 输出: [1,2]

#include <vector>
#include <unordered_set>
using namespace std;

/* 摩尔投票法的变形
不能用哈希表，因为空间复杂度会超
每次都拿走3个不一样的数, 那么最后留下来的有可能是结果，还要再遍历一遍加以验证
时间复杂度：O(n)
空间复杂度：O(1)
*/
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return {};
        int candidate1{0}; // 候选人1的下标
        int candidate2{0}; // 候选人2的下标
        int count1{0}; // 候选人1的数量
        int count2{0}; // 候选人2的数量
        //第1阶段 成对抵销
        for (int i{0}; i < n; ++i) {
            if (nums[i] == nums[candidate1]) ++count1;
            else if (nums[i] == nums[candidate2]) ++count2;
            else if (count1 == 0) {
                candidate1 = i;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = i;
                count2 = 1;
            } else {
                --count1;
                --count2;
            }
        }
        //第2阶段 重新计数 数目要超过三分之一
        count1 = 0;
        count2 = 0;
        for (const int& num : nums) {
            if (num == nums[candidate1]) ++count1;
            else if (num == nums[candidate2]) ++count2;
        }
        vector<int> res{};
        if (count1 > n/3) res.push_back(nums[candidate1]);
        if (count2 > n/3) res.push_back(nums[candidate2]);
        return res;
    }
};

